/**
 * author:Neil
 * Time: 14:44
 * Date: 2022/9/5
 * Description:
 */

/**
 * 二分查找法
 */
public class RecursionBinarySearch {

    public static int recursionBinarySearch(int[] arr,int key,int low,int high){
        if (key < arr[low] || key > arr[high] || low > high){
            return -1;
        }
        int middle = (low + high) / 2;
        if (arr[middle]>key){
            //左边区域
            return recursionBinarySearch(arr,key,low,middle - 1);
        }else if (arr[middle]>key){
            //右边区域
            return recursionBinarySearch(arr,key,middle + 1 ,high);
        }else{
            //最终位置
            return arr[middle];
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,3,5,7,9,11,15,18,19,56,115,228,336,445};
        int key = 11;
        int position = recursionBinarySearch(arr,key,0,arr.length - 1);

        if(position == -1){
            System.out.println("查找的是"+key+",序列中没有该数！");
        }else{
            System.out.println("查找的是"+key+",找到位置为："+position);
        }
    }
}
